package thired.algorithm;

import java.util.ArrayList;
import java.util.Arrays;

public class NtoTwo {
    //给定一个整数n 和一个整数k 输出k个各任意2的n次幂组成n，如无法组成返回{}
    public static int[] NtoTwo(int n,int k){
        int index = 0;
        int x = n;
        while (n!=0) {
            int b = n & (-n);
            index = (int) (Math.log(b) / Math.log(2.0));
            n = n - b;
        }
        n = x;
        int[] nums = new int[index + 1];
        nums[nums.length - 1] = 1;
        for (int i = 0; i < nums.length; i++) {
            nums[i] = (int) Math.pow(2,(nums.length - 1 - i));
        }
        String[] res =  process(nums,0,n,null,k) == null ? null  : process(nums,0,n,null,k).split(",") ;
        if(res == null){
            return new int[]{};
        }
        int[] end = new int[res.length];
        for (int i = 0; i < res.length; i++) {
            end[i] = Integer.parseInt(res[i]);
        }
        return end;
    }

    public static String process(int[] nums,int index,int n,String res,int k){
        if(k == 0 && n == 0){
            return res;
        }
        if(k == 0 || index == nums.length || n < 0){
            return null;
        }
        for (int i = index; i < nums.length; i++) {
        String p1 = process(nums,index,n - nums[index],res == null ? String.valueOf(nums[i]) : res + "," + nums[i],k-1);
        String p2 = process(nums,index + 1,n,res,k);
        if(p1 != null){
            return p1;
        }
        if(p2 != null){
            return p2;
        }
        }
        return null;
    }

    public static void main(String[] args) {
        int[] nums = NtoTwo(10,3);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println(" ");
    }
}
